package dynamic.barcutting;

/**
 * 钢条切割问题
 *
 * @author 罗俊华
 * @date 2021/7/21 - 8:47 上午
 */
public class BarCutting {

    /**
     * 获得钢条的最大收益
     *
     * @param lengthMappingPriceMap index=0时，没有意义，index>=1时，index代表钢条的长度，对应的
     *                              lengthMappingPriceMap[index] 代表，该钢条长度下，该钢条的收益是多少
     * @param length                所指定的钢条长度
     * @return 该钢条长度下的最大收益是
     */
    public static int getMaximumProfit(int[] lengthMappingPriceMap, int length) {

        if (length == 0) {
            // 当钢条长度为0时，是没有收益的
            return 0;
        }

        int profit = 0;

        // 这里从i=1开始的原因是：lengthMappingPriceMap中index=0的情况没有意义
        for (int i = 1; i <= length; i++) {

            profit = Math.max(profit,
                    lengthMappingPriceMap[i] + getMaximumProfit(lengthMappingPriceMap, length - i)
            );
        }

        return profit;

    }

    public static void main(String[] args) {

        // index=0的元素，即0在这里没有实际意义
        int[] lengthMappingPriceMap = new int[]{0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
        for (int i = 1; i < 11; i++) {
            int maximumProfit = getMaximumProfit(lengthMappingPriceMap, i);


            System.out.println(maximumProfit);
        }

    }
}
